ランダム評価を用いたPCS multiproofs

多項式コミットメントの多重証明スキーム

この記事では、（加法的同型性を持つ）多項式コミットメントスキームの多重証明スキームについて説明します。この方式は、検証が非常に効率的であり、また、すべての多項式が完全に利用可能である限り、証明計算も効率的である

検証者の主要な操作は1回の多項式演算だけ

データにアクセスすることなく、証明のみから集計を行わなければならない場合には適していない

そのため、弱いステートレスを実現する目的でのverkle triesの設定には非常に強力

KZGコミットメント方式は、2つのコミットメントを足して2つの多項式の和への公約を得ることが可能な、あらゆる「加法的同型」の方式にも有効なので、Inner product argument (bulletproofsの中核となる議論)にも適用可能であり、実際にこのユースケースでは非常に強力な集約スキームとなっている

ランダム評価を使用したVerkle multiproofs

問題：幅dのVerkle trieにおいて，すべての中間KZG（「Kate」）証明をできるだけ効率的に提供したい．

すべての中間的なcommitmentを提供する必要があり、Verkle trieではそれを回避する方法はないが、単一のKZG証明に最適化できる。KZGについては、すべての証明が検証者に与えられれば、効率的な多重検証技術があるが、できるだけ少ない定数の証明で済ませたいのですわ

verkle triesへの接続

https://scrapbox.io/files/60ee8778d177730022f57961.png

葉のvalue 0101 0111 1010 1111 -> 1213(緑)を証明するためには、ノードAとノードB（シアン）にコミットメントを与え、さらに以下のKZG証明をしなければならない。

ノード0101 0111 1010 1111 -> 1213のルート（キーと値のハッシュ）が，インデックス1010におけるインナーノードBのコミットメントの評価であることの証明

インナーノードBのルート（KZGコミットメントのハッシュ）が，インデックス0111におけるインナーノードAのコミットメントの評価であることの証明

インナーノードAのルート（KZGコミットメントのハッシュ）がインデックス0101におけるルートのコミットメントの評価であることの証明

ωはd-th root of unityで、これにより多くの演算が実際にはより効率的になる

Hは衝突耐性のあるハッシュ関数を意味し、例えばsha256など

もしツリーの内側にノードがあれば（パスの内側のノードが多ければ）、提供すべき証明の数は増える。

証明との関係

verkle multiproof（同時に多くの葉を証明するverkle proof）の中心部分は、次の関係を証明すること

$ f_0(z_0)=y_0

$ f_{m-1}(z_{m-1})=y_{m-1}

証明

このとき、証明者は以下の計算を実行する。

$ g(X)= r^0 \frac{f_0(X)-u_0}{X-z_0}+r^1 \frac{f_1(X)-u_1}{X-z_1}+・・・+r^{m-1} \frac{f_{m-1}(X)-u_{m-1}}{X-z_{m-1}}

u is なに？

これ、全てのインデックスにおけるなに？

これは、商のランダムな線形結合なことに由来する。もし、商をただ足すだけなら、2つの商がその余りを「相殺」して多項式になるだけということもありえる

なるほど、rってそういう意味ね

多項式(コミットメント)のコミットメント的な

1.

上式を2つに分割すると次のようになる

$ g(t)=\underbrace{\sum^{m-i}_{i=0}{r^i}\frac{{f_i}(t)}{t-z_i}}_{g_1(t)}-\underbrace{\sum^{m-i}_{i=0}{r^i}\frac{y_i}{t-z_i}}_{g_2(t)}

第1項は、コミットメントにオープニングを与えることで計算できる(?)

$ E=\sum^{m-i}_{i=0}\frac{{r^i}}{t-z_i}C_i

$ π=[(h(s)-y)/(s-t)]_1

$ ρ=[(g(s)−w)/(s−t)]_1

検証

1つのグループ要素を保存するための変更

上記の両方のKZG proofsは同じ点にあるため、それらを集約して1つのグループ要素と1つのペアとして保存できる

なんで、、同じ点ならそれができる？

$ q=H(E,D,y,ω)

最適化：評価形式ですべてを行う

上記のバージョンのKZG multiproofの大きな利点は、証明者と検証者の作業の大部分をその場で行うだけで済むというもの

さらに、これらの操作はすべて、多項式の評価形式（数学用語で言うと「ラグランジュ基底」）で行うことができる。

これが何を意味するのか、どのように使われるのかを以下に説明する

評価形式

ここでは、多項式を見るもう一つの方法、いわゆる「評価形式」を定義する

$ {all polynomicals of degree < d }↔︎{vectors of length d, seen as evaluations of a polynomial at ω^i}

このようにして、次のような一対一の対応が成り立ちます。

実際、上述のKZG多項式のすべての演算は、評価形式で非常に効率的に行うことができます。

ラグランジュ多項式

ラグランジュ多項式を定義しましょう

$ ℓ_i(X)=\prod_{i≠j}\frac{X-ω^ij}{ω^i-ω^j}

$ ℓ_i(x) = \left\{ \begin{array}{l}\displaystyle {1} \;\;\; (\; x=ω^i ) \\0 \;\;\; ( otherwise )\end{array} \right.

$ f(X)=\sum^{d-1}_{i=0}{y_il_i(X)}

評価形式の多項式は、これにちなんで「ラグランジュ基底の多項式」と呼ばれる

$ [f(s)]_1 = \sum^{d-1}_{i=0} y_i[ℓ_i(s)]_1

評価形式と係数形式の間で変更するFFT

$ u_i= \sum^{d-1}_{j=0}{v_jω^{ij}}

$ v_i=\frac{1}{d} \sum^{d-1}_{j=0}{u_jω^{-ij}}

DFTが多項式の評価値を係数形式で計算するのと同様に、逆DFTは多項式の評価値からその係数を計算します。

厳密には，DFTは演算の総称であり，FFTはそれを実装するためのアルゴリズムである（sortが演算であり，quicksortがその演算を実装するための1つの可能なアルゴリズムであるのと同様である）。しかし、口語では、演算とアルゴリズムの両方を意味する場合でも、FFTと言うことが非常に多い。

多項式の乗算と除算

$ h_i=h(ω^i)=f(ω^i)g(ω^i)=f_ig_i

$ q_i=q(ω_i)=f(ω_i)/g(ω_i)=f_i/g_i

ポイントの1つがゼロのときに分割する

$ q(X)=\frac{f(X)}{g(X)}=\frac{f(X)}{X-ω^m}=\sum^{d-1}_{i=0}{f_i}\frac{l_i(X)}{X-ω^m}

$ A(X)=x^d-1=\prod^{d-1}_{i=0}{X-ω^i}

Aの形式微分は次のように与えられる

$ A'(X)=dx^{d-1}=\sum^{d-1}_{j=0}\prod_{i≠j}{X-ω^i}

$ A'(X)=d(ω^i)^{d-1}=dω^{-1}

この多項式は、ラグランジュ多項式を次のように記述できる

$ ℓ_i(X)=\frac{1}{A^′(ωi)}\frac{A(X)}{X−ω^i}=\frac{1}{dω^{−i}}\frac{A(X)}{X−ω^i}=\frac{ω^i}{d}\frac{A(X)}{X−ω^i}

つまり

$ \frac{l_i(X)}{X-ω^m}=\frac{ω^i}{d}\frac{A(X)}{(X−ω^i)(X−ω^m)}=\frac{ω^i}{ω^m}\frac{l_m(X)}{(X−ω^i)}

$ q(X)=\sum^{d-1}_{i=0}f_i\frac{l_i(X)}{X-ω^m}\frac{ω^i}{ω^m}\frac{l_im(X)}{X-ω^m}

$ q_m=q(ω^m)=\sum^{d-1}_{i=0}f_i\frac{ω^i}{ω^m}\frac{1}{ω^m-ω^i}\sum^{d-1}_{i=0}f_i\frac{ω^{i-m}}{ω^m-ω^i}

$ q_j=q(ω^j)=\sum^{d-1}_{i=0}f_i\frac{l_i(ω^j)}{ω^j-ω^m}=\frac{f_j}{ω^j-ω^m}

ドメイン外の点で評価形式の多項式を評価する

係数形式の多項式で出来ることの中に、評価形式では簡単に実現できないことがある。それは、任意の点で評価すること

しかし、領域外の点zでfを評価するためには、まず係数形式に変換しなければならないのではないか？

そこで登場するのが、いわゆる偏心式。ここでは、ラグランジュ補間を用いてこの公式を導く方法を紹介する

$ f(z)=\sum^{d-1}_{i=0}{f_il_i(z)}=\sum^{d-1}_{i=0}{\frac{ω^i}{d}}{\frac{A(z)}{z-ω^i}}= \frac{A(z)}{d}\sum^{d-1}_{i=0}{f_i}{\frac{ω^i}{z-ω^i}}=\frac{z^d-1}{d}\sum^{d-1}_{i=0}{f_i}{\frac{ω^i}{z-ω^i}}